package com.hmdp.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static List<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        int length = candidates.length;
        Arrays.stream(candidates).sorted();
        combine(candidates,length, 0,target,0);
        return result;
    }
    static List<Integer> path = new ArrayList<>();
    static List<ArrayList<Integer>> result = new ArrayList<>();
    public static void combine(int[] candidates, int length, int sum, int tar,int index) {
        if (candidates.length == 0 )
            return;
        if (sum == tar ){
            result.add(new ArrayList<Integer>(path));
            System.out.println("正确的:"+path);
            return;
        }
        if (sum > tar ){
            return;
        }

        for (int i =index ;i<length&&sum<tar;i++) {
            path.add(candidates[i]);
            sum = sum + candidates[i];
            combine(candidates,length,sum,tar, i);
            sum = sum - candidates[i];
            path.remove(path.size()-1);
        }
    }

}
